package danran.dp;

import java.util.Arrays;

/**
 * @Classname CanPartition
 * @Description TODO
 * @Date 2021/9/1 10:45
 * @Created by ASUS
 */
public class CanPartition {

    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int[][] dp = new int[len][len];
        for (int i = len - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < len; j++) {
                if (s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                else
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][len - 1];
    }

    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if ((sum % 2) != 0)
            return false;
        // 从数组中选择某些元素求和得到 target = sum / 2
        int target = sum / 2;
        boolean[][] dp = new boolean[nums.length + 1][target + 1];
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = true;
        }
        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j <= target; j++) {
                // dp[i][j]表示数到第i个数字的时候，背包的容量为j能否实现
                dp[i][j] = dp[i - 1][j]; // 不放入背包中，结果和前一个数的结果一致
                if (j >= nums[i - 1]) {
                    dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
                }
            }
        }
        return dp[dp.length - 1][target];
    }

}
